// https://leetcode.cn/problems/path-with-maximum-gold/description/

// 算法思路总结：
// 1. 深度优先搜索寻找黄金矿工最大收益路径
// 2. 从每个有黄金的格子开始DFS探索所有可能路径
// 3. 使用path变量记录当前路径黄金总量
// 4. 回溯时恢复path和vis状态，探索不同路径
// 5. 实时更新最大收益值ret
// 6. 时间复杂度：O(4^k)，空间复杂度：O(m×n)

#include <iostream>
using namespace std;

#include <vector>
#include <cstring>
#include <algorithm>

class Solution 
{
public:
    int dx[4] = {-1, 0, 1, 0};
    int dy[4] = {0, 1, 0, -1};
    int m, n, ret, path;
    bool vis[101][101];
    bool haveGold[101][101];

    int getMaximumGold(vector<vector<int>>& grid) 
    {
        m = grid.size(), n = grid[0].size();
        ret = 0, path = 0;
        memset(vis, 0, sizeof(vis));
        memset(haveGold, 0, sizeof(haveGold));

        for (int i = 0 ; i < m ; i++)
        {
            for (int j = 0 ; j < n ; j++)
            {
                if (grid[i][j] > 0)
                {
                    haveGold[i][j] = true;
                }
            }
        }

        for (int i = 0 ; i < m ; i++)
        {
            for (int j = 0 ; j < n ; j++)
            {
                if (haveGold[i][j] == true)
                {
                    dfs(grid, i, j);
                }
            }
        }

        return ret;
    }

    void dfs(vector<vector<int>>& grid, int a, int b)
    {
        path += grid[a][b];
        vis[a][b] = true;

        ret = max(ret, path);
        for (int i = 0 ; i < 4 ; i++)
        {
            int x = a + dx[i], y = b + dy[i];
            if (x >= 0 && y >= 0 && x < m && y < n && vis[x][y] == false && haveGold[x][y] == true)
            {
                dfs(grid, x, y);
            }
        }
        
        path -= grid[a][b];
        vis[a][b] = false;
    }
};

int main()
{
    vector<vector<int>> grid1 = {
        {0, 6, 0},
        {5, 8, 7},
        {0, 9, 0}
    };

    vector<vector<int>> grid2 = {
        {1, 0, 7},
        {2, 0, 6},
        {3, 4, 5},
        {0, 3, 0},
        {9, 0, 20}
    }; 

    Solution sol;

    cout << sol.getMaximumGold(grid1) << endl;
    cout << sol.getMaximumGold(grid2) << endl;

    return 0;
}